package com.leetcode;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-18 10:38
 * @version: 1.0
 * @description: 给定一个经过编码的字符串，返回它解码后的字符串。
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * 思路：将所有字符入栈，遇到 ] 开始计算， 并把计算后的结果在入栈，直到 字符串遍历完成且栈空
 **/
public class DecodeString {

    int index = 0;

    public String decodeString(String s) {
        LinkedList<String> linkedList = new LinkedList<>();
        while (index < s.length()){
            if (Character.isDigit(s.charAt(index))){ //向队列中添加数字
                String digit = dealDigit(s);
                linkedList.addLast(digit);
            }else if(Character.isLetter(s.charAt(index)) || "[".equals(String.valueOf(s.charAt(index)))){ // 添加字符
                linkedList.addLast(String.valueOf(s.charAt(index)));
                index++;
            }else {
                LinkedList<String> sub = new LinkedList<>();
                while (!"[".equals(linkedList.peekLast())) {
                    sub.addFirst(linkedList.pollLast());
                }
                linkedList.removeLast(); // 移除 [
                String str = dealStr(sub);
                StringBuilder sb = new StringBuilder();
                int digit = Integer.parseInt(linkedList.removeLast());

                for (int i = digit;i > 0 ; i--){
                    sb.append(str);
                }
                linkedList.addLast(sb.toString());
                index++;
            }
        }

        return dealStr(linkedList);

    }

    private String dealStr(LinkedList<String> sub) {
        StringBuilder sb = new StringBuilder();
        for (String s : sub) {
            sb.append(s);
        }
        return sb.toString();
    }

    private String dealDigit(String s) {
        StringBuilder sb = new StringBuilder();
        while (Character.isDigit(s.charAt(index))){
            sb.append(s.charAt(index));
            index++;
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String s = "2[ac2[bc]]z";
        DecodeString decodeString = new DecodeString();
        System.out.println(decodeString.decodeString(s));
    }


    /**
     * 第20题，有效括号问题
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '('){
                stack.push(')');
            }else if(c == '{'){
                stack.push('}');
            }else if(c == '['){
                stack.push(']');
            }else {

                if (stack.isEmpty()){
                    return false;
                }else {
                    Character pop = stack.pop();
                    if (pop != c) return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
